public class demo1 {
    class Solution {
        public String longestPalindrome(String s) {
            int n=s.length();
            boolean[][]dp=new boolean[n][n];
            int len=0;
            String ret="";
            for(int i=n-1;i>=0;i--){
                for(int j=i;j<n;j++){
                    if(s.charAt(i)==s.charAt(j)){
                        dp[i][j]=i+1<j?dp[i+1][j-1]:true;
                    }
                    if(dp[i][j]){
                        if(j-i>=len){
                            len=j-i;
                            ret=s.substring(i,j);
                        }
                    }
                }
            }
            return ret;
        }
    }
}
